package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

/**
 * @ClassName MaxProfit
 * @Description MaxProfit
 * @Author wanghaiwei
 * @Date 2022/11/28 11:29
 */
public class MaxProfit {
    public int maxProfit(int[] prices) {
        if (prices == null) {
            return 0;
        }
        int size = prices.length;
        //max是前i个元素最大的收益
        int max = 0;
        //dp[i]是前i个元素中最小的结果
        int[] dp = new int[size];
        dp[0] = prices[0];
        /**
         * 前i天的最小价格：dp[i] = min{dp[i-1],prices[i]}
         * 前i天的最大收益：max[i] = max{prices[i]-dp[i], max[i-1]}
         */
        for (int i = 1; i < size; i++) {
            dp[i] = Math.min(dp[i-1], prices[i]);
            max = Math.max(prices[i]-dp[i], max);
        }
        return max;
    }

    public static void main(String[] args) {
        MaxProfit solution = new MaxProfit();
        Assert.isTrue(5 == solution.maxProfit(new int[]{7,1,5,3,6,4}), "[7,1,5,3,6,4]计算错误");
        Assert.isTrue(0 == solution.maxProfit(new int[]{7,6,4,3,1}), "[7,6,4,3,1]计算错误");
    }
}
